// 版权所有2011 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package syntax

// Simplify返回一个与re等价但没有重复计数的regexp 
// 以及其他各种简化，例如重写/（？：a+）
// 结果regexp将正确执行，但其字符串表示
// 将不会生成相同的解析树，因为捕获括号
// 可能已被复制或删除。例如，简化形式
// For/（x）{1,2}/is/（x）（x）？/但两个括号都表示为1美元。
// 返回的regexp可以与原始regexp共享结构，也可以是原始regexp。
func (re *Regexp) Simplify() *Regexp {
	if re == nil {
		return nil
	}
	switch re.Op {
	case OpCapture, OpConcat, OpAlternate:
		// 简化子项，如果子项发生变化，则构建新的Regexp。
		nre := re
		for i, sub := range re.Sub {
			nsub := sub.Simplify()
			if nre == re && nsub != sub {
				// 开始复制。ABCFDG 
				nre = new(Regexp)
				*nre = *re
				nre.Rune = nil
				nre.Sub = append(nre.Sub0[:0], re.Sub[:i]...)
			}
			if nre != re {
				nre.Sub = append(nre.Sub, nsub)
			}
		}
		return nre

	case OpStar, OpPlus, OpQuest:
		sub := re.Sub[0].Simplify()
		return simplify1(re.Op, re.Flags, sub, re)

	case OpRepeat:
		if re.Min == 0 && re.Max == 0 {
			return &Regexp{Op: OpEmptyMatch}
		}

		sub := re.Sub[0].Simplify()

		// x{n，}表示x的至少n个匹配项。
		if re.Max == -1 {
			// 特例：x{0，}是x*。
			if re.Min == 0 {
				return simplify1(OpStar, re.Flags, sub, nil)
			}

			// 特例：x{1，}是x+。
			if re.Min == 1 {
				return simplify1(OpPlus, re.Flags, sub, nil)
			}

			// 一般情况：x{4，}是xxxx+。
			nre := &Regexp{Op: OpConcat}
			nre.Sub = nre.Sub0[:0]
			for i := 0; i < re.Min-1; i++ {
				nre.Sub = append(nre.Sub, sub)
			}
			nre.Sub = append(nre.Sub, simplify1(OpPlus, re.Flags, sub, nil))
			return nre
		}

		// 上面处理了特殊情况x{0}。

		// 特例：x{1}就是x。
		if re.Min == 1 && re.Max == 1 {
			return sub
		}

		// 一般情况：x{n，m}意味着x的n个副本和x的m个副本？
		// 如果我们嵌套最后的m个副本，机器将做更少的工作，
		// 这样x{2,5}=xx（x（x）？）？

		// 构建前导前缀：xx。
		var prefix *Regexp
		if re.Min > 0 {
			prefix = &Regexp{Op: OpConcat}
			prefix.Sub = prefix.Sub0[:0]
			for i := 0; i < re.Min; i++ {
				prefix.Sub = append(prefix.Sub, sub)
			}
		}

		// 构建并附加后缀：（x（x）？？）？
		if re.Max > re.Min {
			suffix := simplify1(OpQuest, re.Flags, sub, nil)
			for i := re.Min + 1; i < re.Max; i++ {
				nre2 := &Regexp{Op: OpConcat}
				nre2.Sub = append(nre2.Sub0[:0], sub, suffix)
				suffix = simplify1(OpQuest, re.Flags, nre2, nil)
			}
			if prefix == nil {
				return suffix
			}
			prefix.Sub = append(prefix.Sub, suffix)
		}
		if prefix != nil {
			return prefix
		}

		// 一些退化情况，如min>max或min<max<0。
		// 处理为不可能匹配。
		return &Regexp{Op: OpNoMatch}
	}

	return re
}

// simplify1为一元操作星、
// OpPlus和OpQuest运算符实现简化。它返回简单的regexp 
// 等价于
// 
// regexp{Op:Op，Flags:Flags，Sub:{Sub}}
// 
// 假设Sub已经很简单，而
// 不首先分配该结构。如果要返回的regexp 
// 与re等价，那么simplify1 
// 将返回re。
// 
// simplify1被排除在Simplify之外，因为其他运算符的实现
// 会生成这些一元表达式。
// 让他们调用simplify1确保他们生成的表达式简单。
func simplify1(op Op, flags Flags, sub, re *Regexp) *Regexp {
	// 特殊情况：尽可能多地重复空字符串，但仍然是空字符串。
	if sub.Op == OpEmptyMatch {
		return sub
	}
	// 如果标志匹配，则运算符是幂等的。
	if op == sub.Op && flags&NonGreedy == sub.Flags&NonGreedy {
		return sub
	}
	if re != nil && re.Op == op && re.Flags&NonGreedy == flags&NonGreedy && sub == re.Sub[0] {
		return re
	}

	re = &Regexp{Op: op, Flags: flags}
	re.Sub = append(re.Sub0[:0], sub)
	return re
}
